什么是HashMap |
您所在的位置：网站首页 › map 是什么 › 什么是HashMap |
什么是HashMap
|
什么是HashMap
HashMap 是一种快速的查找并且插入、删除性能都良好的一种 K/V键值对的数据结构，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。 HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。 HashMap的底层在JDK1.8之前采用数组+链表组成，用(n - 1) & hash找到数组索引位置，如果冲突则使用拉链法解决。在JDK1.8之后的HashMap初始数据结构仍采用数组+链表，当某个桶链表的长度大于8时，会先调用treeifyBin()方法，这个方法会判断数组长度是否小于64，如果大于或等于则执行转换红黑树操作，以减少搜索时间；反之则调用resize()进行扩容。 HashMap的底层数据结构 JDK1.8 之前底层采用数组+链表，用(n - 1) & hash找到数组索引位置，若冲突则用拉链法解决冲突。 拉链法 简单来说就是将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
底层初始数据结构仍采用数组+链表，当某个桶链表的长度大于8时，会先调用treeifyBin()方法，这个方法会判断数组长度是否小于64，如果大于或等于则执行转换红黑树操作，以减少搜索时间；反之则调用resize()进行扩容。 JDK1.8的数据结构示意图如下：
其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素如果链表长度>8&数组大小>=64，链表转为红黑树如果红黑树节点个数>> 16)判断table是否为空或者长度为0，如果是则调用resize()方法扩容。根据哈希值计算确定元素存放在哪个桶中，如果桶为空，则直接插入桶中，否则覆盖。判断tab[i]是否为树节点，是则在树中插入节点，否则在链表中插入节点。如果链表插入节点时阈值大于等于8，则需要将链表转为红黑树。所有元素处理完后，判断是否超过阈值;++size > threshold，超过则扩容。HashMap的put方法源码和注解都在下方，读者可自行debug调试理解下。 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // table未初始化或者长度为0，进行扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 桶中已经存在元素（处理hash冲突） else { Node e; K k; // 判断table[i]中的元素是否与插入的key一样，若相同那就直接使用插入的值p替换掉旧的值e。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断插入的是否是红黑树节点 else if (p instanceof TreeNode) // 放入树中 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 不是红黑树节点则说明为链表结点 else { // 在链表最末插入结点 for (int binCount = 0; ; ++binCount) { // 到达链表的尾部 if ((e = p.next) == null) { // 在尾部插入新结点 p.next = newNode(hash, key, value, null); // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法 // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。 // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // 跳出循环 break; } // 判断链表中结点的key值与插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等，跳出循环 break; // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 p = e; } } // 表示在桶中找到key值、hash值与插入元素相等的结点 if (e != null) { // 记录e的value V oldValue = e.value; // onlyIfAbsent为false或者旧值为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 e.value = value; // 访问后回调 afterNodeAccess(e); // 返回旧值 return oldValue; } } // 结构性修改 ++modCount; // 实际大小大于阈值则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; } get方法的流程了解吗？老样子，先看流程图：
为了HashMap 存取高效，尽量减少碰撞，数据分配均匀，hash值能够充分的散列。hash值范围很大（-2147483648 到 2147483647），只要哈希函数映射的比较松散，一般很难出现碰撞。但直接使用哈希值内存放不下，那么能直接想到的是使用hash值%数组大小定位位置，而HashMap使用hash值和（数组大小 - 1）做位与运算，计算元素在数组中的索引（与前面算法效果一致，但效率高）。 与运算(&)的用途：清零，即两个二进制数，有一位是0，那么得到的数就是0。hash值是不固定的，它的二进制数有0有1，想尽量减少碰撞，那么需要保证与运算(&)的值全为1，这样能保证最后运算结果完全取决于hash值，一个（2^n）-1的数得到的二进制数就都是1，例如（16-1）的二进制是1111。 HashMap的扩容了解吗？HashMap是基于数组+链表和红黑树实现的，但是初始化容量是固定的，默认为16。 static final int DEFAULT_INITIAL_CAPACITY = 1 |
【本文地址】